#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* prv_ptr = head;
        ListNode* ptr = head->next;
        while (ptr != nullptr) {
            if (ptr->val >= prv_ptr->val) {
                ptr = ptr->next;
                prv_ptr = prv_ptr->next;
                continue;
            }
            ListNode* ptr_next = ptr->next;
            if (ptr->val <= head->val) {
                ptr->next = head;
                head = ptr;
                prv_ptr->next = ptr_next;
                ptr = ptr_next;
                continue;
            }
            ListNode* iter_prv = head;
            ListNode* iter = head->next;
            while (iter != ptr) {
                if (ptr->val > iter_prv->val && ptr->val <= iter->val) {
                    iter_prv->next = ptr;
                    ptr->next = iter;
                    prv_ptr->next = ptr_next;
                    ptr = ptr_next;
                    break;
                }
                iter_prv = iter_prv->next;
                iter = iter->next;
            }
        }
        return head;
    }
};


int main() {
    Solution solution;
    ListNode l1(-1), l2(5), l3(3), l4(4), l5(0);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = &l5;
    ListNode* head = solution.insertionSortList(&l1);
    cout << endl;
}